package cn.xaut.优先队列;

import cn.xaut.剑指offer.m01.ListNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 23. 合并K个升序链表
 */
public class demo23 {

    public ListNode mergeKLists(ListNode[] lists) {

        List<Integer> list = new ArrayList<>();
        for (ListNode node : lists) {
            while (node != null) {
                list.add(node.val);
                node = node.next;
            }
        }
        Collections.sort(list);
        ListNode dummyHead = new ListNode(-1);
        ListNode pre = dummyHead;
        for (int x : list) {
            pre.next = new ListNode(x);
            pre = pre.next;
        }
        return dummyHead.next;
    }

    // 优先队列
    public ListNode mergeKLists2(ListNode[] lists) {
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (ListNode cur : lists) {
            while (cur != null) {
                pq.offer(cur.val);
                cur = cur.next;
            }
        }

        ListNode dummyHead = new ListNode(-1);
        ListNode pre = dummyHead;
        while (!pq.isEmpty()) {
            pre.next = new ListNode(pq.poll());
            pre = pre.next;
        }
        return dummyHead.next;
    }
    
    public static void main(String[] args) {

    }
}
